1994 IOI Problems

DAY 1 PROBLEMS

DAY 1 - PROBLEM 1

          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5

Fig. 1

Figure 1 shows a number triangle. Write a program that calculates 
the highest sum of numbers passed on a route that starts at the top 
and ends somewhere on the base.

* Each step can go either diagonally down to the left or diagonally 
down to the right.

* The number of rows in the triangle is > 1 but <= 100.

* The number in the triangle, all integers are between 0 and 99 
inclusive.

In the example above the route through 7,3,8,7,5 produces the 
highest sum 30. 

INPUT DATA
Data about the number of rows in the triangle are first read from 
the INPUT.TXT file followed by the rows of the triangle.

In our example, INPUT.TXT appears as follows:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

OUTPUT DATA
The highest sum is written as an integer in the OUTPUT.TXT file. 
In our example this file would contain the number 30. 




DAY 1 - PROBLEM 2

   1   2   3   4   5   6   7
 *****************************
1*       *       *           *
 ****	 *****   *    ****   *
2*  *        *   *    *  *   *
 *  *****    *****    ****   * 
3*           *   *    *  *   *
 *  **********   ******  *   *
4*  *                    *   *
 *****************************
Fig 1.(string of *'s is a wall) 

  N
W + E
  S


Figure 1 shows the map of a castle. Write a program that calculates
1) The number of rooms in the castle.
2) The size in modules of the largest room.
3) Which wall to remove from the castle (joining two existing rooms) 
to make as large a room as possible.

The castle is divided into a grid of square modules m rows by n 
columns ( m<= 50, n<=50).  Each module can have from zero to four 
walls, inclusive.

INPUT.TXT

The map is stored in the INPUT.TXT file in the form of numbers, one 
for each module.

* The file starts with the number of modules in the north-south 
direction and the number of modules in the east-west direction.

* In the following lines each module is described by a number 
(0<=p<=15). This number is the sum of: 1 (= wall to the west), 2 (= 
wall to the north), 4(=wall to the east), 8(=wall to the south). 
Inner walls are defined twice, a wall to the south in module 1,1 is 
also indicated as a wall to the north in module 2,1. The module at 
position 1,1 has a west, north and south wall so the sum is 1 + 2 + 
8 = 11.

* The castle always has at least two rooms.

INPUT.TXT for our example:
4
7
11  6  11  6   3  10  6
7   9  6  13   5  15  5
1   10 12  7  13   7  5
13  11 10  8  10  12  13

OUTPUT DATA

In the OUTPUT.TXT file, the following are written on three lines:
1) The number of rooms.
2) The area of the largest room counted in modules.
3) A suggestion of which wall to remove that will join two existing 
room to make as large a room as possible (first the row and then the 
column of the module next to the wall and finally the compass 
direction that points to the wall).  There may be more than one but 
you need only choose one to display.

("4 1 E" is one of several possibilities)

5
9
4 1 E

The last line refers to the removing the wall pointed to below.

   1   2   3   4   5   6   7
 *****************************
1*       *       *           *
 ****	 *****   *    ****   *
2*  *        *   *    *  *   *
 *  *****    *****    ****   * 
3*           *   *    *  *   *
 *  **********   ******  *   *
4*->*                    *   *
 *****************************
Fig 2.(remove wall on the East wall of 
       module 4 1) 



DAY 1 - PROBLEM 3

  1  1  3  5  1
  3  3  2  0  3
  3  0  3  2  3
  1  4  0  3  3
  3  3  3  1  1

Fig. 1

Figure 1 shows a square. Each row, each column and the two diagonals 
can be read as a five digit prime number. The rows are read from 
left to right. The columns are read from top to bottom. Both 
diagonals are read from left to right. 
Using the data in the INPUT.TXT file, write a program that 
constructs such squares.

* The prime numbers must have the same digit sum (11 in Fig. 1)

* The digit in the top left-hand corner of the square is pre-
determined (1 in the Fig.1).

* A prime number many be used more than once in the same square.

* If there are several solutions, all must be presented.

* A five-digit prime number cannot begin with zeros, i.e. 00003 is 
NOT a five digit prime number.

Input data

The program reads data from the INPUT.TXT file. First the digit sum 
of prime numbers and then the digit in the top left-hand corner of 
the square. The file contains two lines. There will always be a 
solution to the given test data. In our example:
11
1

Output data
In the OUTPUT.TXT file, write five lines for each solution found, 
where each line in turn consists of a five digit prime number. The 
above example has 3 solutions which means that the OUTPUT.TXT file 
contains the following (the empty line between the different 
solutions is optional):

1 1 3 5 1
1 4 0 3 3 
3 0 3 2 3 
5 3 2 0 1
1 3 3 1 3

1 1 3 5 1
3 3 2 0 3 
3 0 3 2 3 
1 4 0 3 3 
3 3 3 1 1 

1 3 3 1 3 
1 3 0 4 3 
3 2 3 0 3
5 0 2 3 1
1 3 3 3 1


DAY 2 PROBLEMS

DAY 2 Problem 1
           

  3  3  0
  2  2  2
  2  1  2

Figure 1 (Dial Positions)

The nine numbers in figure 1 represent the position of 9 dials where 
each dial has one of four positions North or 12 o'clock (0) , East 
or 3 o'clock (1), South or 6 o'clock (2) and West or 9 o'clock (3).

      0
    3-+-1
      2


There are 9 different ways to turn the dials on the clocks. Each way 
is called a move. Each move is selected by a number from 1 to 9. 
That number will turn the dials marked by a 1  90 degrees clockwise. 
Those marked with a 0 have no affect. The nine moves are displayed 
in figure 2 below.

1  1  0      1  1  1     0  1  1
1  1  0      0  0  0     0  1  1
0  0  0      0  0  0     0  0  0
Move 1       Move 2      Move 3

1  0  0      0  1  0     0  0  1
1  0  0      1  1  1     0  0  1
1  0  0      0  1  0     0  0  1
Move 4       Move 5      Move 6

0  0  0      0  0  0     0  0  0
1  1  0      0  0  0     0  1  1
1  1  0      1  1  1     0  1  1
Move 7       Move 8      Move 9

For example the following sequence of moves has the corresponding 
affect on the dials (they all end up at 12 o'clock (0).

  3  3  0            3  0  0 
  2  2  2  Move 5 -> 3  3  3  Move 8 ->
  2  1  2            2  2  2
           
  3  0  0            0  0  0
  3  3  3  Move 4 -> 0  3  3  Move 9 ->
  3  3  3            0  3  3

  0  0  0
  0  0  0
  0  0  0

The problem is write a program that will take any starting position 
for the clock and find the shortest sequence of moves which puts all 
the dials in the 12 o'clock (0) position.

INPUT DATA
Read nine numbers from the INPUT.TXT file. The example above will 
have the input data file:

3  3  0
2  2  2
2  1  2

OUTPUT DATA

Write to the OUTPUT.TXT file the shortest sequence of moves 
(numbers), which turns all the dials to the 0 or 12 o'clock 
position. In our example the OUTPUT.TXT file could look as follows:

5849 

Only one solution is required.

 


Day 2 Problem 2

A man arrives at a bus stop at 12:00. He remains there during 12:00 
- 12:59. The bus stop is used by a number of bus routes. The man 
notes the times of arriving buses. The times when buses arrive are 
given with the following rules:

1) Buses on the same route arrive at regular intervals from 12:00 to 
12:59.

2) Times are given in whole minutes from 1 to 59.

3) Each bus route has at least 2 buses arriving at the station 
between 12 and 12:59.

4) The number of bus routes in the test example will be <= 17.

5) Buses from different routes may arrive at the same time.

6) Several bus routes can have the same time of first arrival and/or 
time interval. If two bus routes have the same starting time and 
interval, they are distinct and are both to be presented.

Find the fewest number of bus routes that must stop at the bus stop 
to satisfy the input data. For each bus route, output the starting 
time and the interval. 

INPUT DATA

The input file, INPUT.TXT, contains a number n (n<= 300) telling how 
many arriving buses have been noted, followed by the arrival times 
in ascending order.

Out example:

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53 


If two buses arrive at the same time, that time is listed twice.

OUTPUT DATA

Write a table to the OUTPUT.TXT file with one line for each bus 
route. Each line in the file give the time of arrival for the first 
bus and the time interval in minutes. The order of the bus routes 
does not matter. If there are several solutions, only one is 
required.
Our example gives:
0 13
3 12
5 8


DAY 2 Problem 3

Consider the magic list of 5 numbers

1 3 10 2 5

Any two number that are next to each other are considered neighbors. 
Also the two end numbers 1 and 5 as neighbors as if the list formed 
a circle of numbers. Starting with 2, we can form an unbroken 
sequence of integers from 2 to 21 using a single number in the list 
or by adding neighbors. Here is how the sequence is formed:

2, 3, 1+3=4, 5, 5+1=6, 2+5=7, 2+5+1=8, 5+1+3=9, 10, 2+5+1+3=11, 
10+2=12, 3+10=13, 1+3+10=14,
3+10+2=15, 1+3+10+2=16, 10+5+2=17, 10+2+5+1=18,
5+1+3+10=19, 3+10+2+5=20, 1+3+10+2+5=21

You were given three number (n, m, and k) where 

n= the length of the list of numbers
m= the starting number
k= (smallest possible value for a member of the
    list, i.e. all numbers must be greater or
    equal to k).

Your task is to choose n integers for the magic list where an 
unbroken sequence of all integers m, m+1, m+2,....max can be 
generated where max is as large as possible.

INPUT DATA

The INPUT.TXT file contains three integers (n,m,k). For the example 
the file would be:

5
2
1

OUTPUT DATA

The file OUTPUT.TXT must contain:

1) The highest number (max) that can be generated with the list of 
numbers.

2) All arrangements of numbers in a circle that produce a sequence 
from m to max. (One per line.) Each arrangement is a list of numbers 
starting with the smallest number (which is not necessarily unique.)

Note: 2 10 3 1 5 is not a valid solution, since it does not start 
with the smallest number. 
(1 3 10 2 5) and (1 5 2 10 3) must both be included in the output. 
Note that (1 1 2 3), 
(1 3 2 1), (1 2 3 1) and ( 1 1 3 2) should all be output.

The output for our example would be:

21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4



